package backtrack

func generateParenthesis(n int) []string {
	res := []string{}
	dfs("", 0, 0, &res, n)
	return res
}

func dfs(cur string, left, right int, res *[]string, n int) {
	if left == n && right == n {
		*res = append(*res, cur)
		return 
	}
	if left < right {
		return 
	}
	if left < n {
		dfs(cur + "(", left + 1, right, res, n)
	}
	if right < n {
		dfs(cur + ")", left, right + 1, res, n)
	}
}